package org.example;

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Test {

    public static void quicksort(int[] arr){
        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int left, int right){
        if(left > right){
            return;
        }
        int midIndex = partition(arr, left, right);
        sort(arr, 0, midIndex - 1);
        sort(arr, midIndex + 1, right);
    }

    public static int partition(int[] arr, int left, int right){
        int mid = (left + right) / 2;
        while (right > left){
            while (right > left && arr[right] >= arr[mid]){
                right--;
            }
            while (right > left && arr[left] < arr[mid]){
                left++;
            }
            swap(arr, left, right);
        }
        return right;
    }
    public static void swap(int[] arr, int tmp1, int tmp2){
        int tmp = arr[tmp1];
        arr[tmp1] = arr[tmp2];
        arr[tmp2] = tmp;
    }

    public static void shellSort(int[] arr) {
        int len = arr.length;
        for (int gap = len / 2; gap >= 1; gap = gap / 2) {
            for (int i = 0; i < gap; i++) {
                for(int j = i; j < len; j++){
                    int val = arr[j];
                    int k = j;
                    while (k >= gap && arr[k - gap] > val){
                        arr[k] = arr[k - gap];
                        k -= gap;
                    }
                    arr[k] = val;
                }
            }
        }
    }



    public static void insertsort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            int val = arr[i], j = i;
            while (j >= 1 && val < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = val;
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,2,2,2,1,0,5,2,1,8,4,2};
        quicksort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static  int[] solve(int[] arr){
        int n = arr.length;
        Stack<Integer> stack = new Stack<>();
        boolean[] hash = new boolean[n + 1];
        int aim = n;
        int[] ret = new int[n];
        int i = 0;
        for(int num : arr){
            stack.push(num);
            hash[num] = true;
            while (hash[aim]){
                aim--;
            }
            while (!stack.isEmpty() && stack.peek() > aim){
                ret[i++] = stack.pop();
            }
        }
        return ret;
    }

    public static void main23(String[] args) {
//        int[] arr = {2,4,1,5,3};
//        int[] ret = solve(arr);
//        System.out.println(Arrays.toString(ret));
        Integer a = 1;
        int b = 1;
        if(a.equals(b)){
            System.out.println("yes");
        }else {
            System.out.println("no");
        }
    }

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] c1 = in.nextLine().toCharArray();
        int len = c1.length;//
        char[] c2 = new char[2 * len - 1];
        for(int i = 0; i < len; i++){
            c2[i] = c1[i];
        }
        for(int i = len; i < 2 * len - 1; i++){
            c2[i] = c1[2 * i - len - 1];
        }
        long num = 0;
        for(int i = 0; i < 2 * len - 1; i++){
            num = num * 10 + c2[i] - '0';
        }
        if(isprime(num)){
            System.out.println("prime");
        }else{
            System.out.println("noprime");
        }
    }

    private static boolean isprime(long num){
        long sqrt = (long)Math.sqrt(num);
        for(long i = 2; i <= sqrt; i++){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }
}
